πŸ’‘ ν•΄μ‹œ ν…Œμ΄λΈ” (Hash Table)

@Seongukbaek Posted May 06, 2022 Β· Updated May 06, 2022 Β· 12 min read

🧷 ν•΄μ‹œ ν…Œμ΄λΈ”

μ™„μ „ νƒμƒ‰μœΌλ‘œλŠ” μ‹œκ°„μ΄ˆκ³Όμ— λΉ μ§€κ²Œ λ˜λŠ” λ¬Έμ œμ—μ„œλŠ” ν•΄μ‹œλ₯Ό μ μš©μ‹œμΌœ 탐색 μ‹œκ°„μ„ 쀄일 수 μžˆλ‹€.

Hash λŠ” λ‚΄λΆ€μ μœΌλ‘œ 배열을 μ‚¬μš©ν•˜μ—¬ 데이터λ₯Ό μ €μž₯ν•˜μ—¬ μž‘μ€ λ©”λͺ¨λ¦¬λ‘œλ„ ν”„λ‘œμ„ΈμŠ€ 관리가 κ°€λŠ₯ν•΄μ§€κ³ , λΉ λ₯Έ 검색 속도λ₯Ό κ°–λŠ”λ‹€. 고유의 index 둜 μ ‘κ·Όν•˜μ—¬ νŠΉμ • 값을 νƒμƒ‰ν•˜κΈ°μ— ν‰κ· μ μœΌλ‘œ O(1)O(1)이 λœλ‹€.

  • 좩돌 ν˜„μƒμœΌλ‘œ 인해 "평균적"으둜 O(1)O(1)이닀.
  • λ¬Έμ œλŠ” 이 index 둜 μ €μž₯λ˜λŠ” key 값이 λΆˆκ·œμΉ™ν•˜λ‹€λŠ” 점이닀.

좩돌 ν˜„μƒ : μ„œλ‘œ λ‹€λ₯Έ 두 개의 Key κ°€ 같은 index 둜 ν•΄μ‹±λ˜μ–΄ 같은 곳에 μ €μž₯ν•˜λ €λŠ” ν˜„μƒ

κ·Έλž˜μ„œ "νŠΉλ³„ν•œ μ•Œκ³ λ¦¬μ¦˜"을 μ‚¬μš©ν•˜μ—¬ μ €μž₯ν•  데이터와 μ—°κ΄€λœ κ³ μœ ν•œ 숫자λ₯Ό λ§Œλ“€μ–΄ 이λ₯Ό index 둜 μ‚¬μš©ν•œλ‹€.

  • index λŠ” κ·Έ λ°μ΄ν„°λ§Œμ˜ κ³ μœ ν•œ μœ„μΉ˜μ΄λ―€λ‘œ, μ‚½μž…μ΄λ‚˜ μ‚­μ œ μ—°μ‚° μ‹œ 좔가적인 λΉ„μš©μ΄ λ°œμƒν•˜μ§€ μ•ŠλŠ”λ‹€.
  • μ—¬κΈ°μ„œ νŠΉλ³„ν•œ μ•Œκ³ λ¦¬μ¦˜μ€ Hash Method or Hash Function 이라고 ν•˜κ³ , 이 ν•¨μˆ˜μ— μ˜ν•΄ λ°˜ν™˜λœ λ°μ΄ν„°μ˜ 고유 숫자 값을 Hash Code 라고 ν•œλ‹€.
  • ν•˜μ§€λ§Œ, 잘λͺ»λœ Hash Function 을 톡해 좩돌 ν˜„μƒμ΄ λ°œμƒν•˜κ²Œ 될 수 μžˆλ‹€.

    • 좩돌 ν˜„μƒμ΄ λ§Žμ•„μ§ˆμˆ˜λ‘, 탐색에 ν•„μš”ν•œ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(N)O(N)에 κ°€κΉŒμ›Œμ§€κ²Œ λœλ‹€.

쒋은 Hash Function 은 일반적으둜, Key 의 일뢀뢄을 μ°Έμ‘°ν•˜μ—¬ ν•΄μ‹œ 값을 λ§Œλ“€μ§€ μ•Šκ³ , Key 전체λ₯Ό μ°Έμ‘°ν•˜μ—¬ ν•΄μ‹œ 값을 λ§Œλ“ λ‹€.

  • ν•˜μ§€λ§Œ μ΄λŠ” Key 의 νŠΉμ„±μ— 따라 λ‹¬λΌμ§€κ²Œ λœλ‹€.

Hash Function 을 무쑰건 1:1 맀칭으둜 λ§Œλ“œλŠ” 것보닀, 좩돌 ν˜„μƒμ„ μ΅œμ†Œν™”ν•˜λŠ” λ°©ν–₯으둜 이λ₯Ό μ–΄λ–»κ²Œ λŒ€μ‘ν•  것인가가 더 μ€‘μš”ν•˜λ‹€.

  • 1:1 λŒ€μ‘μ΄ λ˜λ„λ‘ λ§Œλ“œλŠ” 것은 거의 λΆˆκ°€λŠ₯ν•˜κ³ , κ°€λŠ₯ν•˜λ‹€ν•΄λ„ μ΄λŠ” κ³§ λ°°μ—΄κ³Ό 같기에 λ©”λͺ¨λ¦¬ μ‚¬μš©μ΄ λ§Žμ•„μ§„λ‹€.

πŸͺš 좩돌 ν˜„μƒ ν•΄κ²° 방법

μ•„λž˜ 2κ°€μ§€ 방법이 있고, 두 방법 λͺ¨λ‘ μ΅œμ•…μ˜ 경우 O(M)O(M)의 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.

  1. Open Address 방식 (개방 μ£Όμ†Œλ²•) : 좩돌 ν˜„μƒμ΄ λ°œμƒν•˜λ©΄, (즉, 이미 ν•΄λ‹Ή ν•΄μ‹œ 버킷이 μ‚¬μš© 쀑인 경우) λ‹€λ₯Έ ν•΄μ‹œ 버킷에 μ‚½μž…ν•˜λ €λŠ” 데이터λ₯Ό μ‚½μž…ν•˜λŠ” 방식이닀.

    • μ΄λ•Œ, 데이터λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•΄ λΉ„μ–΄ μžˆλŠ” λ‹€λ₯Έ ν•΄μ‹œ 버킷을 μ°Ύμ•„ 헀맨닀.
    • μ΅œμ•…μ˜ 경우, λΉ„μ–΄ μžˆλŠ” ν•΄μ‹œ 버킷을 μ°Ύμ§€ λͺ»ν•΄ λ‹€μ‹œ 탐색을 μ‹œμž‘ν•œ μœ„μΉ˜λ‘œ λŒμ•„μ˜¬ 수 μžˆλ‹€. μ΄λ•Œ νƒμƒ‰ν•˜λŠ” 데도 μ•„λž˜ 3κ°€μ§€ 방법이 μžˆλ‹€.
    • Linear Probing: 순차적으둜 νƒμƒ‰ν•˜λŠ” 방식

      • Primary Clustering에 μ·¨μ•½ν•˜λ‹€.
    • Quadratic Probing: 2μ°¨ ν•¨μˆ˜λ₯Ό μ΄μš©ν•΄ 탐색할 μœ„μΉ˜λ₯Ό μ°ΎλŠ”λ‹€. (121^2, 222^2, 323^2, ... 으둜 νƒμƒ‰μœ„μΉ˜ 증가)

      • Secondary Clustering에 μ·¨μ•½ν•˜λ‹€.
    • Double Hashing Probing: ν•˜λ‚˜μ˜ ν•΄μ‹œ ν•¨μˆ˜μ—μ„œ 좩돌이 λ°œμƒν•˜λ©΄ 2μ°¨ ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄ 탐사 이동폭을 μ–»μ–΄ λ‹€λ₯Έ 버킷을 νƒμƒ‰ν•œλ‹€.

      • 두 취약점을 ν•΄κ²°ν•˜μ§€λ§Œ, κ°€μž₯ λ§Žμ€ 연산을 μš”κ΅¬ν•œλ‹€.

ν•΄μ‹œ 버킷? : 데이터λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•œ 곡간

  1. Separate Chaining 방식 (뢄리 연결법) : 일반적으둜 Open Address방식은 Separate Chaining보닀 λŠλ¦¬λ‹€. Open Address의 경우 ν•΄μ‹œ 버킷을 μ±„μš΄ 밀도가 λ†’μ•„μ§ˆμˆ˜λ‘ μ΅œμ•…μ˜ κ²½μš°κ°€ λ°œμƒν•  λΉˆλ„κ°€ λ†’μ•„μ§€κΈ° λ•Œλ¬Έμ΄λ‹€. 반면, Separate Chaining 방식은 보쑰 ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄ 잘 μ‘°μ •ν•œλ‹€λ©΄ μ΅œμ•…μ˜ κ²½μš°μ— κ°€κΉŒμ›Œμ§€λŠ” λΉˆλ„λ₯Ό 쀄일 수 μžˆλ‹€. Separate Chaining 방식은 2κ°€μ§€ κ΅¬ν˜„ 방식이 μžˆλ‹€.

    • μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜λŠ” 방식 (Linked List)

      • 각각의 버킷을 μ—°κ²° 리슀트둜 λ§Œλ“€μ–΄ 좩돌이 λ°œμƒν•˜λ©΄ ν•΄λ‹Ή λ²„ν‚·μ˜ list에 μΆ”κ°€ν•˜λŠ” 방식이닀.
      • μ—°κ²° 리슀트의 μž₯, 단점을 κ·ΈλŒ€λ‘œ 이어 λ°›μ•„, μ‚­μ œ λ˜λŠ” μ‚½μž…μ΄ κ°„λ‹¨ν•˜μ§€λ§Œ, μž‘μ€ 데이터듀을 μ €μž₯ν•  λ•Œ μ—°κ²° 리슀트 자체의 μ˜€λ²„ν—€λ“œκ°€ λ°œμƒν•œλ‹€.
      • 버킷을 κ³„μ†ν•΄μ„œ μ‚¬μš©ν•˜λŠ” Open Address 방식에 λΉ„ν•΄ ν…Œμ΄λΈ”μ˜ ν™•μž₯을 늦좜 수 μžˆλ‹€λŠ” νŠΉμ§•μ΄ μžˆλ‹€.
    • Treeλ₯Ό μ‚¬μš©ν•˜λŠ” 방식 (Red-Black Tree)

      • μ—°κ²° 리슀트 λŒ€μ‹  트리λ₯Ό μ‚¬μš©ν•˜λŠ” λ°©μ‹μœΌλ‘œ, μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν• μ§€, 트리λ₯Ό μ‚¬μš©ν• μ§€ κ²°μ •ν•˜λŠ” 기쀀은 ν•˜λ‚˜μ˜ ν•΄μ‹œ 버킷에 ν• λ‹Ήλœ key-value 쌍의 κ°œμˆ˜μ΄λ‹€.
      • 트리의 기본적인 λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 많기 λ•Œλ¬Έμ—, λ°μ΄ν„°μ˜ κ°œμˆ˜κ°€ 적닀면 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜λŠ” 것이 νš¨μœ¨μ μ΄λ‹€.
      • λ°μ΄ν„°μ˜ κ°œμˆ˜κ°€ 적을 λ•Œ, μ„±λŠ₯μƒμ˜ μ°¨μ΄λŠ” 거의 없기에 λ©”λͺ¨λ¦¬μ μœΌλ‘œ 효율적인 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜λŠ” 것이 μ’‹λ‹€.

Java 7μ—μ„œλŠ” Separate Chaining 방식을 μ‚¬μš©ν•΄ HashMap 을 κ΅¬ν˜„ν•œλ‹€.

  • Open Addressing은 데이터 μ‚­μ œ μ‹œ, remove() 의 λΉˆλ²ˆν•œ 호좜둜 인해 μ²˜λ¦¬κ°€ 효율적이기 μ–΄λ ΅λ‹€.
  • λ˜ν•œ, μ €μž₯된 ν‚€-κ°’ 쌍의 κ°œμˆ˜κ°€ 일정 이상이면, Worst Case λ°œμƒ λΉˆλ„κ°€ 더 λ†’μ•„μ Έ Separate Chaining 방식보닀 λŠλ¦¬λ‹€.

데이터가 μ λ‹€λŠ” κ²ƒμ˜ 의미 : 기쀀은 μœ„μ—μ„œ μ–ΈκΈ‰ν–ˆλ“― ν•˜λ‚˜μ˜ ν•΄μ‹œ 버킷에 ν• λ‹Ήλœ key-value 쌍의 κ°œμˆ˜μ΄λ‹€. μ—°κ²° 리슀트의 κΈ°μ€€κ³Ό 트리의 기쀀은 6κ°œμ™€ 8개둜 λ‚˜λ‰œλ‹€.

  • 7이 μ—†λŠ” μ΄μœ λŠ”, 자료ꡬ쑰λ₯Ό λ³€κ²½ν•˜λŠ” 데 μ†Œλͺ¨λ˜λŠ” λΉ„μš©μ„ 쀄이기 μœ„ν•¨μ΄λ‹€.

ν•΄μ‹œ 버킷에 6개의 key-value 쌍이 μžˆλ‹€κ³  κ°€μ •ν•΄λ³΄μž. μ΄λ•Œ ν•˜λ‚˜μ˜ 값이 μΆ”κ°€λ˜μ–΄ 총 쌍의 κ°œμˆ˜κ°€ 7κ°œκ°€ λ˜μ—ˆλ‹€. λ§Œμ•½, 기쀀이 6, 7μ΄μ—ˆλ‹€λ©΄, 값이 μΆ”κ°€λ˜λ©΄μ„œ 자료ꡬ쑰λ₯Ό 트리둜 λ³€κ²½ν•΄μ•Ό ν•œλ‹€. 그리고 λ‹€μ‹œ ν•˜λ‚˜μ˜ 값이 μ‚­μ œλœλ‹€λ©΄, λ‹€μ‹œ νŠΈλ¦¬μ—μ„œ μ—°κ²° 리슀트둜 자료ꡬ쑰λ₯Ό λ³€κ²½ν•΄μ•Ό ν•œλ‹€.

  • 즉, 기쀀이 1 차이가 λ‚œλ‹€λ©΄, 자료ꡬ쑰λ₯Ό λ³€κ²½ν•˜λŠ” Switching λΉ„μš©μ΄ λ„ˆλ¬΄ 많이 ν•„μš”ν•˜κ²Œ λœλ‹€.
  • λ”°λΌμ„œ, 기쀀을 2만큼의 차이λ₯Ό λ‘μ—ˆλ‹€.
  • 결과적으둜, 쌍의 κ°œμˆ˜κ°€ 6개 -> 7개둜 λ³€κ²½λœλ‹€λ©΄ μ—°κ²° 리슀트 ꡬ쑰λ₯Ό μœ μ§€ν•  것이고, 8개 -> 7개둜 λ³€κ²½λœλ‹€λ©΄ 트리 ꡬ쑰λ₯Ό μœ μ§€ν•  것이닀.

보쑰 ν•΄μ‹œ ν•¨μˆ˜ : key 의 ν•΄μ‹œ 값을 λ³€ν˜•ν•˜μ—¬ ν•΄μ‹œ 좩돌 κ°€λŠ₯성을 쀄이기 μœ„ν•΄ μ‚¬μš©ν•œλ‹€. Separate Chaining 방식 μ‚¬μš© μ‹œ, ν•¨κ»˜ μ‚¬μš©λ˜λ©° μ΅œμ•…μ˜ κ²½μš°μ— κ°€κΉŒμ›Œμ§€μ§€ μ•Šλ„λ‘ ν•œλ‹€.

πŸͺš ν•΄μ‹œ 버킷 동적 ν™•μž₯ (Resize)

ν•΄μ‹œ λ²„ν‚·μ˜ κ°œμˆ˜κ°€ 적닀면 λ©”λͺ¨λ¦¬ μ‚¬μš©μ„ μ•„λ‚„ 수 μžˆμ§€λ§Œ ν•΄μ‹œ 좩돌둜 인해 μ„±λŠ₯ 상 손싀이 λ°œμƒν•œλ‹€.

  • κ·Έλž˜μ„œ HashMap 은 key-value 쌍의 κ°œμˆ˜κ°€ 일정 이상이 되면, ν•΄μ‹œ λ²„ν‚·μ˜ 개수λ₯Ό 두 배둜 λŠ˜λ¦°λ‹€. 개수λ₯Ό 늘림으둜써, 좩돌둜 μΈν•œ μ„±λŠ₯ 손싀 문제λ₯Ό μ–΄λŠ 정도 ν•΄κ²°ν•  수 μžˆλ‹€.

    • μ—¬κΈ°μ„œ 일정 μ΄μƒμ˜ μ˜λ―ΈλŠ” ν˜„μž¬ λ°μ΄ν„°μ˜ κ°œμˆ˜κ°€ ν•΄μ‹œ λ²„ν‚·μ˜ 개수의 75% κ°€ 될 λ•Œμ΄λ‹€.
    • 0.75 λΌλŠ” μˆ«μžλŠ” load factor둜 λΆˆλ¦°λ‹€.

πŸͺš 예제 문제

문제 링크

N(1 ~ 100000)의 κ°’λ§ŒνΌ λ¬Έμžμ—΄μ΄ μž…λ ₯λœλ‹€. 처음 μž…λ ₯λ˜λŠ” λ¬Έμžμ—΄μ€ "OK", λ“€μ–΄μ˜¨ 적이 있던 λ¬Έμžμ—΄μ€ "λ¬Έμžμ—΄ + index"둜 좜λ ₯ν•œλ‹€.

// input 5 abcd bac abcd abcd ab // output OK OK abcd1 abcd2 OK
  • N값은 μ΅œλŒ€ 10λ§Œμ΄λ―€λ‘œ, 이λ₯Ό μ™„μ „ νƒμƒ‰μœΌλ‘œ ν•΄κ²°ν•œλ‹€λ©΄ O(N2)O(N^2)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό κ°€μ Έ, 100μ–΅λ²ˆμ˜ 연산이 ν•„μš”ν•˜λ‹€. μ΄λŠ” κ³§λ°”λ‘œ μ‹œκ°„μ΄ˆκ³Όλ‘œ μ΄μ–΄μ§ˆ 것이닀.
  • λ”°λΌμ„œ ν•΄μ‹œ ν…Œμ΄λΈ”μ„ μ΄μš©ν•΄ ν•΄κ²°ν•΄μ•Ό ν•œλ‹€.

    • μž…λ ₯된 λ¬Έμžμ—΄ 값을 ν•΄μ‹œ ν‚€λ‘œ λ³€ν™˜μ‹œμΌœ μ €μž₯ν•˜λ©΄μ„œ μ§„ν–‰ν•œλ‹€.
public class Solution { static final int HASH_SIZE = 1000; static final int HASH_LEN = 400; static final int HASH_VAL = 17; // μ†Œμˆ˜λ‘œ ν•  것, 주둜 17, 19, 23 static String str; static int N; static int[][] data = new int[HASH_SIZE][HASH_LEN]; static int[] length = new int[HASH_SIZE]; static String[][] s_data = new String[HASH_SIZE][HASH_LEN]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); N = Integer.parseInt(br.readLine()); // μž…λ ₯ 수 (1 ~ 100000) for (int i = 0; i < N; i++) { str = br.readLine(); // μž…λ ₯ λ¬Έμžμ—΄λ‘œλΆ€ν„° ν‚€ 값을 생성 int key = getHashKey(str); // ν•΄λ‹Ή ν‚€ 값이 이미 μ‘΄μž¬ν•˜λŠ”μ§€ 확인 int cnt = checking(key); // 이미 λ“€μ–΄μ™”λ˜ λ¬Έμžμ—΄ if(cnt != -1) sb.append(str).append(cnt).append("\n"); else sb.append("OK").append("\n"); } System.out.println(sb.toString()); } public static int getHashKey(String str) { int key = 0; // ν‚€ κ°’ 생성 (HASH_VAL μ‚¬μš©) for (int i = 0; i < str.length(); i++) key = (key * HASH_VAL) + str.charAt(i) + HASH_VAL; // ν‚€ κ°’ μ–‘μˆ˜λ‘œ λ³€ν™˜ if(key < 0) key = -key; return key % HASH_SIZE; } public static int checking(int key) { // ν˜„μž¬ 킀에 λ‹΄κΈ΄ 수 int len = length[key]; // 이미 λ“€μ–΄μ˜¨ 적 있음 if(len != 0) { // 이미 λ“€μ–΄μ˜¨ λ¬Έμžμ—΄μ΄ ν•΄λ‹Ή ν‚€ 배열에 μžˆλŠ”μ§€ 확인 for (int i = 0; i < len; i++) { if(str.equals(s_data[key][i])) { // μžˆλ‹€λ©΄ λ“€μ–΄μ˜¨ 수λ₯Ό λ°˜ν™˜ data[key][i]++; return data[key][i]; } } } // λ“€μ–΄μ˜¨ 적이 μ—†μ—ˆμœΌλ©΄ ν•΄λ‹Ή ν‚€ 배열에 λ¬Έμžμ—΄μ„ μ €μž₯ν•˜κ³  길이 1 늘리기 s_data[key][length[key]++] = str; // λ“€μ–΄μ˜¨ 적 μ—†μ—ˆλ‹€λ©΄ -1 λ°˜ν™˜ return -1; } }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€